package Hot_100;

import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/*
    括号生成
    https://leetcode.cn/problems/generate-parentheses/
    数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
* */
public class T22_generateParenthesis {
    @Test
    public void test1() {
//        System.out.println(generateParenthesis_DFS(3));
        System.out.println(generateParenthesis_BFS(3));
    }

    public List<String> generateParenthesis_DFS(int n) {
        ArrayList<String> result = new ArrayList<>();
        backtracking(n, result, 0, 0, "");
        return result;
    }

//  ----------------------------------DFS----------------------------------
    private void backtracking(int n, List<String> result, int left, int right, String str) {
        if (right > left) {           //如果右边括号大于左边
            return;
        }
        if (left == n && right == n) {//符合条件
            result.add(str);
            return;
        }
        if (left < n) {     //要生成左分支，先看左边括号是否还有剩余
            backtracking(n, result, left + 1, right, str + "(");
        }
        if (right < left) { //右括号数量少于左括号 (前面已经判断right<left)
            backtracking(n, result, left, right+1, str + ")");
        }
    }


//  ----------------------------------BFS------------------------------------------------
    public List<String> generateParenthesis_BFS(int n) {
        List<String> res = new ArrayList<>();   //存储所有合法的情况
        if (n == 0) {
            return res;
        }
        Queue<Node> queue = new LinkedList<>();  //队列
        queue.offer(new Node("", n, n));     //入队

        while (!queue.isEmpty()) {          //当队列不为空
            Node curNode = queue.poll();    //出队
            if (curNode.left == 0 && curNode.right == 0) {  //得到一种解法
                res.add(curNode.res);
            }
            if (curNode.left > 0) {        //当左括号有剩余
                queue.offer(new Node(curNode.res + "(", curNode.left - 1, curNode.right));
            }
            if (curNode.right > 0 && curNode.left < curNode.right) { //当右括号有剩余并且 左括号的剩余量小于右括号的剩余量
                // （即左边括号大于右边）
                queue.offer(new Node(curNode.res + ")", curNode.left, curNode.right - 1));
            }
        }
        return res;
    }

    class Node {
        /**
         * 当前得到的字符串
         */
        private String res;
        /**
         * 剩余左括号数量
         */
        private int left;
        /**
         * 剩余右括号数量
         */
        private int right;

        public Node(String str, int left, int right) {
            this.res = str;
            this.left = left;
            this.right = right;
        }
    }
}



